1. Field of the Invention
The invention relates to the field of solid model classification and searching. In particular it relates to method and system for classifying and searching solid models using a learning algorithm.
2. Description of the Related Technology
Solid models are the critical data elements in modern Computer-Aided Design (CAD) environments, describing the shape and form of parts and assemblies. Increasingly, manufacturing enterprises maintain vast databases (also known as knowledge-bases) of Computer-Aided Design information as well as computer aided manufacturing (CAM) and Computer-Aided Process Planning (CAPP) information associated with the solid models. Such information includes, in addition to the solid models of the parts and assemblies, numeric control (NC) machining programs, production plans and cost data associated with manufacturing the parts and assemblies.
CAD, CAM and CAPP information of previously designed parts and assemblies is useful for process planning and cost estimation of new parts. Such information is generally sought based on perceived similarity of shape and/or structure and/or manufacturing process. However, many existing database systems storing solid models index the solid models based only on simple properties that have little to do with the structure or shape of the part, i.e. part name, designer's name, bills of materials etc. and do not use content and shape-based analysis of the solid models to index the solid models.
A problem in CAD has been the diversity and heterogeneity of representation formats for the shape information. At a fundamental level, Constructive Solid Geometry (CSG) and Boundary Representation Models (BRep) serve as a foundation for most modeling systems and applications. While BReps dominate the CAD industry, the mathematical details of the representation vary widely by system. Hence, even when data translation works well, there is little to guarantee that the resulting solid models can be directly compared.
Two types of BReps dominate the commercial CAD environment: NURBS-based BReps (e.g., SDRC, Pro/E, where NURBS are the primary internal representation) and those dominated by analytic Surface BReps (e.g. Parasolid, ACIS, where analytic surfaces CO-exist with NURBS). Comparing CAD models for indexing across these formats can be very difficult requiring considerable amounts of special-case algorithms for each different representation. Therefore, it is necessary to have a uniform methodology to interact with CAD data in engineering information management systems in order to alleviate the problems caused by the diversity of representation formats.
In the engineering field, indexing of parts and part families had been done with group technology (GT) coding. Group technology was designed to facilitate process planning and cell-based manufacturing by imposing a classification scheme on individual machined parts. These techniques were developed prior to the advent of inexpensive computer technology; hence they are not rigorously defined and are intended for human, not machine, interpretation. Some of the early work on feature identification from solid models aimed to find patterns in model databases or automate the GT coding process. The common aspect of all of these techniques is that they are all post priori: one runs their algorithm on model and it produces the category or label for it. This raises issues such as changing categorization schemes and whether or not an entirely new algorithm is needed to compensate for such changes.
There are two basic types of approaches for matching and retrieval of 3D CAD data: (1) feature-based techniques and (2) shape-based techniques. The feature-based techniques go back at least as far as the late 1970s to Kyprianou's thesis, and extract engineering features (machining features, form features, etc.) from a solid model of a mechanical part for use in database storage, automated GT coding, etc. Feature-based reasoning was used for the retrieval of solid models for use in variant process planning. It was further examined how to develop graph-based data structures and create heuristic similarity measures among artifacts. This work was extended to manufacturing feature based similarity measurements. These ideas have been integrated with database techniques to enable indexing and clustering of CAD models based on shape and engineering properties.
The shape-based techniques are more recent, owing to research contributions from computational geometry, computer vision and computer graphics. A shape based approach works as the representational “lowest common denominator:” STL or VRML (or other) polygon mesh. From the polygon mesh, measures of similarity can be computed among 3D models. A method has been created for generating an abstraction of a 3D model as a probability distribution of samples from a shape function acting on the model. This technique is generally robust under model degradation. But it is a rigid technique and poor discriminator among model classes because it analyzes gross model shape, rather than the discriminatory features that are common for CAD/CAM data. Additionally, recent published studies have focused on a very limited set of heterogeneous (planes, trees, phones, etc.) and manually-classified 3D graphics, animation and rendering models; a set that does not include any models that are specifically engineering, solid modeling or mechanical CAD oriented.
In the CAD/CAM domain, engineering artifacts can have multiple classifications. For example, discrete machined parts can be classified in to different categories according to different classification criterion, such as functionality (e.g., brackets or fasteners), manufacturing cost, manufacturing process (e.g., casting, machining, forging, molding, etc). FIG. 1 shows four CAD models under two different, but perfectly reasonable, classification schemes. The first classification is based on manufacturing process, where parts are separated into either “3-axis machining” or “casting” processes. In machining, rotating cutting tools remove material based on swept volumes; in this case these sweeps are limited to those on a 3-axis vertical machining center. The second, orthogonal classification is based on mechanical function. FIG. 1 also shows a break down into parts that function as “brackets” and as “housings.” These two different types of classification systems would typically require two different searching algorithms to compensate for the different search criteria. This therefore creates a needless waste of resources.
Therefore, there is a need for a method for classifying solid objects for improved searching that uses a uniform methodology that can handle the complexity of models that are used for engineering components. There is also a need for a method for enabling a model comparison algorithm to adapt to different classifications that are relevant in many engineering applications